Answer:

Here (yet again) are the two parts to recursion:

  1. If the problem is easy, solve it immediately.
  2. If the problem can't be solved immediately, divide it into smaller problems, then:
    • Solve the smaller problems by applying this procedure to each of them.

Factorial Function

You have probably seen the factorial function before. It is defined for all integers greater or equal to zero: 

factorial( 0 ) = 1
factorial( N ) = N * factorial( N-1 )

For example, 

factorial( 5 ) = 5 * factorial( 4 )
               = 5 * ( 4 * factorial( 3 ) )
               = 5 * ( 4 * (3 * factorial( 2 ) ) )
               = 5 * ( 4 * (3 * (2 * factorial( 1 ) ) ) ) 
               = 5 * ( 4 * (3 * (2 * ( 1 * factorial( 0 ) ) ) ) )
               = 5 * ( 4 * (3 * (2 * ( 1 * 1 ) ) ) )
               = 5 * 4 * 3 * 2 * 1 * 1
               = 120

Often factorial(N) is written N!

Examine the definition and check that it includes both of the two parts of a recursive definition.

QUESTION 2:

What is the base case in this definition?

go to previous page   go to home page   go to next page